
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Created by losor on 2017/3/5.
 */
public class _496_NextGreaterElementI {
    public static void main(String[] args) {
        int[] a = {4,1,2};
        int[] b = {1,3,4,2};
        System.out.println(nextGreaterElement(a,b));
    }

    public static int[] nextGreaterElement(int[] findNums, int[] nums) {
        findIndexForFindNums(findNums,nums);
        findNext(findNums,nums);
        return findNums;
    }


    /**大佬写的**/
    public int[] nextGreaterElementBigBoss(int[] findNums, int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            //如果堆栈中存储的上一个数比num小，就吧上一个数给取出来，然后和num一起写道map中
            while (!stack.isEmpty() && stack.peek() < num)
                map.put(stack.pop(), num);
            //把新的num放到栈中
            stack.push(num);
        }
        for (int i = 0; i < findNums.length; i++)
            findNums[i] = map.getOrDefault(findNums[i], -1);
        return findNums;
    }

    public static void findNext(int[] findNums, int[] nums){
        int flag = 0;
        for (int i = 0; i < findNums.length; i++) {
            flag = 0;
            if (findNums[i] == nums.length - 1){
                findNums[i] = -1;
                continue;
            }
            for (int j = findNums[i]; j < nums.length; j++) {
                if (nums[j]>nums[findNums[i]]){
                    findNums[i] = nums[j];
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                findNums[i] = -1;
            }
        }
    }

    public static void findIndexForFindNums(int[] findNums, int[] nums){
        for (int i = 0; i < findNums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == findNums[i]) {
                    findNums[i] = j;
                    break;
                }
            }
        }
    }
}
